package com.kznnc.data_structure.sort;

import java.util.Arrays;

/**
 * @Description 堆树
 * 堆树的底层是可以利用数组作为底层的存储结构
 * 原因 堆树 = 完全二叉树 + (节点 >= 或者 <= 左右子树 )
 * @Author houchenkai
 * @Created Date: 2021/7/22 15:10
 * @ClassName
 */
public class HeapSortDemo {


    public static void main(String[] args) {
        int[] data = {8, 4, 20, 7, 3, 1, 25, 14, 17};
        heapSort(data);
        remove(data);
        System.out.println(Arrays.toString(data));
    }

    public static void heapSort(int[] data) {
        int len = data.length;
        for (int i = len / 2 - 1; i >= 0; i--) {
            maxHeap(data, i, len);
        }
        System.out.println(Arrays.toString(data));
//        for (int i = len - 1; i > 0; i--) {
//            // 大顶堆的堆顶元素是 堆的最大值 i是最后一个元素的位置  在maxHeap中 son < i
//            // 所以将 堆顶元素（i）和 最后的元素进行交换   将剩余的元素 进行堆化再 与 i 进行交换
//            // 所以 交换后的数据都是的有序的
//            int temp = data[0];
//            data[0] = data[i];
//            data[i] = temp;
//            // 这个i能不能理解?
//            // 因为len~i 已经排好序了
//            maxHeap(data, 0, i);
//        }
//        System.out.println(Arrays.toString(data));
    }

    /**
     * 建一个大顶堆, end表示最多建到的点  向上调整
     */
    public static void maxHeap(int[] data, int start, int end) {
        int parent = start;
        // 下标是从0开始的就要加1, 从1就不用
        int son = parent * 2 + 1;
        while (son < end) {
            int temp = son;
            // 比较左右节点和父节点的大小
            if (son + 1 < end && data[son] < data[son + 1]) {
                // 表示 右节点左节点大
                // 就要换右节点跟父节点
                temp = son + 1;
            }
            // temp表示的是 我们左右节点大的那一个
            if (data[parent] > data[temp]) {
                // 不用交换
                return;
            } else {
                // 交换
                int t = data[parent];
                data[parent] = data[temp];
                data[temp] = t;
                // 继续堆化
                // 下次堆化的 parent = 此次堆化的中 parent 左  右 三个节点中 最大的元素的下标
                // 原因：未交换前 parent 2 左 3  右 4  此时4后面的数在大顶堆的原则下是
                parent = temp;
                son = parent * 2 + 1;
            }
        }
        return;
    }


    private static  void remove(int[] data){
        int value =data[data.length-1];
        // 删除时 将最后一个元素 拿到堆顶 进行向下堆化
        // 也可指定下标进行删除 此时index就是 指定元素的下标
        siftDown(data,0,value);
        data[data.length-1] = 0;
    }
    /**
     * 将 value 从index 下标开始向下调整
     *
     * @param index
     * @param data
     */
    private  static  void siftDown(int[] data, int index, int value) {
        int half = data.length >>> 1;
        while (index < half) {
            int child = (index << 1) + 1;
            int c = data[child];
            int right = child + 1;
            if (right < data.length && c < data[right]) {
                c = data[child = right];
            }
            if (value > c) {
                break;
            }
            data[index] = c;
            index = child;

        }
        data[index] = value;
    }

//  int half = size >>> 1;        // loop while a non-leaf
//        while (k < half) {
//            int child = (k << 1) + 1; // assume left child is least
//            Object c = queue[child];
//            int right = child + 1;
//            if (right < size &&
//                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
//                c = queue[child = right];
//            if (key.compareTo((E) c) <= 0)
//                break;
//            queue[k] = c;
//            k = child;
//        }
//        queue[k] = key;
}
